/*
 * SimpleUnaryToUnaryRecursionRemover.java
 *
 * Created on February 20, 2007, 8:41 PM
 *
 * Performs the following transformation iteratively.
 * 
 *    A          A
 *    |    ==>  / \
 *    A         ---
 *   / \
 *   ---
 * 
 * That is, whenever unary recursion to (non-lexical) categories is encountered, 
 * the lower (non-lexical) node is removed and what it dominates is
 * "pulled up" to be immediately dominated by A.  This is done
 * iteratively until what A dominates is not a single category A.
 *
 * In short, it removes vacuous unary recursion.
 */

package galronnlp.util;
import galronnlp.util.SymbolGenerator;
import galronnlp.util.Symbol;
import galronnlp.util.Tree;
import java.util.Iterator;
import java.util.LinkedList;
/**
 *
 * @author Dennis N. Mehay
 */
public class SimpleUnaryToUnaryRecursionRemover implements UnaryToUnaryRecursionRemover {
    private SymbolGenerator gen;
    /** Creates a new instance of SimpleUnaryToUnaryRecursionRemover */
    public SimpleUnaryToUnaryRecursionRemover() {
        this.gen = new SymbolGenerator();
    }

    /** Creates a new instance of SimpleUnaryToUnaryRecursionRemover */
    public SimpleUnaryToUnaryRecursionRemover(SymbolGenerator gen) {
        this.gen = gen;
    }
    
    public Tree removeUnaryProductions(Tree t) {
        if(t.type()==Tree.LEXICAL) { return t; }
        if(!(t.type()==Tree.UNARY)) { 
            Iterator<Tree> children = t.getChildren().iterator();
            LinkedList<Tree> nonUnaryChildren = new LinkedList<Tree>();
            while(children.hasNext()) {
                nonUnaryChildren.addLast(removeUnaryProductions(children.next()));                
            }
            return TreeFactory.makeTree(t.cat(), nonUnaryChildren);
        }
        else {
            Tree tempChild = (Tree)(t.getChildren().getFirst());
            String tCat = t.cat().toString();
            if(tempChild.type()==Tree.LEXICAL) {
                return t;
            } else if(tCat.equals(tempChild.cat().toString())) {
                LinkedList<Tree> tempChildren = tempChild.getChildren();
                while(tempChild.type()==Tree.UNARY && tempChild.cat().toString().equals(tCat)) {
                    tempChild = (Tree)(tempChild.getChildren().getFirst());
                    tempChildren = tempChild.getChildren();
                }
                if(tempChild.type()==Tree.LEXICAL) {
                    return TreeFactory.makeTree(t.cat(), tempChild);
                }
                LinkedList<Tree> nonUnaryChldrn = new LinkedList<Tree>();
                Iterator<Tree> chlds = tempChildren.iterator();
                while(chlds.hasNext()) {
                    nonUnaryChldrn.addLast(removeUnaryProductions(chlds.next()));
                }
                return TreeFactory.makeTree(t.cat(), nonUnaryChldrn);
            }  else { 
                return TreeFactory.makeTree(t.cat(), removeUnaryProductions(tempChild));
            }
        }
    }   
    
} // end class SimpleUnaryRecursionRemover
